package graphesTOTEST;

/** Classe représentant un graphe orienté dont les sommets sont
 * numérotés à partir de 0.
 * @author un client anonyme
 *
 */
public class Graphe {

    /** Matrice d'adjacence du graphe. */
    private int[][] U;
    /** Taille max de la matrice d'incidence du graphe. */
    public int NMAX = 1000;
    /** valid[i] ssi le sommet i appartient au graphe. */ 
    private boolean[] valid;
    /** Constante indiquant une absence d'arc dans la matrice d'adjacence 
     * (l'arc a alors un poid infini). */ 
    public static final int ALPHA_NOTDEF = -1;
	
    /**
     * Cr�e un graphe vide (il y aura un maximum de 1000 sommets) 
     */
    public Graphe() {
	NMAX  = 1000;
	U     = new int [NMAX][NMAX];
	valid = new boolean [NMAX];
	for (int i=0; i < NMAX; i++) {
	    valid[i] = false;	
	    for (int j=0; j < NMAX; j++) {
		U[i][j] = ALPHA_NOTDEF;
	    }
	}
    }
	
    /**
     * Cr�e un graphe en sp�cifiant le nombre maximum de sommets.
     *
     * @param nbs Nombre max de sommets dans le graphe
     */
    public Graphe(int nbs) {
	NMAX  = nbs;
	U     = new int [NMAX][NMAX];
	valid = new boolean [NMAX];
	for (int i=0; i < NMAX; i++) {
	    valid[i] = false;		
	    for (int j=0; j < NMAX; j++) {
		U[i][j] = ALPHA_NOTDEF;
	    }
	}
    }
	
    /**
     * Cr�e un graphe � partir d'une matrice d'adjacence du graphe
     * (matrice carrée tq mat[i][j] vaut ALPHA_NOTDEF si (i,j) n'est
     * pas un arc du graphe, et une autre valeur sinon.
     * 
     * @param mat Matrice (enti�re) d'adjacence du graphe. 
     */
    public Graphe(int[][] mat) {
	NMAX  = 2*mat.length; //On multipli par deux la taille de la matrice pour pouvoir ajouter d'autres sommets...
	U     = new int [NMAX][NMAX];
	valid = new boolean [NMAX];
	for (int i=0; i < NMAX; i++) {
	    
	    //REMPLISSAGE DU TABLEAU VALID
	    if (i < mat.length)
		valid[i] = true;
	    else 
		valid[i] = false;
	    
	    for (int j=0; j < NMAX; j++) {
		
		//REMPLISSAGE DE LA MATRICE U
		if ((i < mat.length) && (j < mat[0].length))
		    U[i][j] = mat[i][j];
		else 
		    U[i][j] = ALPHA_NOTDEF;
	    }
	}
    }
    
	/**
	 * Constructeur de clonage
	 * 
	 * @param g
	 */
	public Graphe(Graphe g) {
		NMAX = g.NMAX;
		U     = new int [NMAX][NMAX];
		valid = new boolean [NMAX];
		for (int i=0; i < NMAX; i++) {
			valid[i] = g.valid[i];		
			for (int j=0; j < NMAX; j++) {
				U[i][j] = g.U[i][j];
			}
		}
	}
	
	/**
	 * @param i : le num�ro du sommet
	 * @return vrai si le sommet existe et faux sinon 
	 */
	public boolean existeSommet(int i) {
		if (i < 0 || i >= NMAX) 
			return false;
		else return valid[i];
	}

	/**
	 * @return le nombre de sommets (valides)
	 */
	public int nbSommet() {
		int cpt = 0; //Compteur du nombre de sommet
		for (int i=0; i<NMAX; i++) {
			if (existeSommet(i))
				cpt++;
		}
		return cpt;
	}
	
	/**
	 * @param i origine de l'arc
	 * @param j extr�mit� de l'arc
	 * @return vrai si l'arc existe et faux sinon
	 */
	public boolean existeArc(int i, int j) {
		return existeSommet(i) && existeSommet(j) && (U[i][j] != ALPHA_NOTDEF); 
	}
	
	/**
	 * @param i origine de l'arc
	 * @param j extr�mit� de l'arc
	 * @return la valeur de l'arc
	 */
	public int getValArc(int i, int j) {
		
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeArc(i, j)) {
			System.out.println("Graphe::getValArc: Erreur : il n'y a pas d'arc entre le sommet "+i+" et le sommet "+ j);
			System.exit(-1);
		}
		
		return U[i][j];
	}
	
	/**
	 * @param i num�ro du sommet
	 * @return vrai si le sommet a �t� ajout� et faux s'il est d�j� pr�sent
	 */
	public boolean ajoutSommet(int i) {
		if (existeSommet(i)) {
			return false;
		}
		else {
			/*PRECONDITION ... DEBUGGAGE*/
			if (i < 0 || i >= NMAX) {
				System.out.println("Graphe::ajoutSommet: Erreur : le sommet est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
				System.exit(-1);				
			}
			valid[i] = true;
			return true;
		}
	}
	
	
	/**
	 * @param i sommet a supprimer
	 * @return vrai si la suppression a bien eu lieu et faux si le sommet n'existait pas
	 */
	public boolean supprimeSommet(int i) {
		/*PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::supprimeSommet: Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}
		if (!existeSommet(i)) {
			return false;
		}
		else { //Le sommet existe et il faut �tre s�r qu'il n'est ni l'origine ni l'extr�mit� d'arc encore existant
			/*PRECONDITION ... DEBUGGAGE*/
			if ((lst_pred(i).length != 0) || (lst_succ(i).length != 0)) {
				System.out.println("Graphe::supprimeSommet: Erreur : le sommet "+i+" est encore connect� � d'autre sommet par des arcs");
				System.exit(-1);
			}
			valid[i] = false;
			return true;
		}
	}
	
	/**
	 * @param i sommet origine
	 * @param j sommet extr�mit�
	 * @param val valeur de l'arc
	 * @return retourne vrai si l'arc a �t� ajout� et faux s'il existe d�j� un arc entre les sommets i et j 
	 */
	public boolean ajoutArc(int i, int j, int val) {
		/*PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::ajoutArc: Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			
		/*PRECONDITION ... DEBUGGAGE*/
		if (j < 0 || j >= NMAX) {
			System.out.println("Graphe::ajoutArc: Erreur : le sommet "+j+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(i)) {
			System.out.println("Graphe::ajoutArc: Erreur : le sommet "+i+" n'existe pas");
			System.exit(-1);								
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(j)) {
			System.out.println("Graphe::ajoutArc: Erreur : le sommet "+j+" n'existe pas");
			System.exit(-1);								
		}
		
		if (existeArc(i,j)) {
			return false;
		}
		else {
			U[i][j] = val;
			return true;
		}
	}

	/**
	 * @param i sommet origine
	 * @param j sommet extr�mit�
	 * @param val valeur de l'arc
	 * @return modifi la valeur de l'arc entre les sommets i et j 
	 */
	public void setValArc(int i, int j, int val) {
		/*PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::setValArc: Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			
		/*PRECONDITION ... DEBUGGAGE*/
		if (j < 0 || j >= NMAX) {
			System.out.println("Graphe::setValArc: Erreur : le sommet "+j+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(i)) {
			System.out.println("Graphe::setValArc: Erreur : le sommet "+i+" n'existe pas");
			System.exit(-1);								
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(j)) {
			System.out.println("Graphe::setValArc: Erreur : le sommet "+j+" n'existe pas");
			System.exit(-1);								
		}
		/*PRECONDITION ... DEBUGGAGE*/		
		if (!existeArc(i,j)) {
			System.out.println("Graphe::setValArc: Erreur : l'arc ("+j+" , "+i+") n'existe pas");
			System.exit(-1);								
		}
		U[i][j] = val;
	}
	
		
	/**
	 * @param i origine de l'arc
	 * @param j extr�mit� de l'arc
	 * @return vrai si l'arc a �t� supprim� et faux si l'arc n'existait pas
	 */
	public boolean supprimeArc(int i, int j) {
		/*PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::supprimeArc("+i+","+j+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			
		/*PRECONDITION ... DEBUGGAGE*/
		if (j < 0 || j >= NMAX) {
			System.out.println("Graphe::supprimeArc("+i+","+j+"): Erreur : le sommet "+j+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(i)) {
			System.out.println("Graphe::supprimeArc("+i+","+j+"): Erreur : le sommet "+i+" n'existe pas");
			System.exit(-1);								
		}
		/*PRECONDITION ... DEBUGGAGE*/
		if (!existeSommet(j)) {
			System.out.println("Graphe::supprimeArc("+i+","+j+"): Erreur : le sommet "+j+" n'existe pas");
			System.exit(-1);								
		}	
		
		if (!existeArc(i,j))
			return false;
		else {
			U[i][j] = ALPHA_NOTDEF;
			return true;
		}		
	}
	
	/**
	 * @param i numero du sommet dont on cherche le degr� n�gatif
	 * @return retourne le nombre d'arcs dont i est l'extremit� (cad retourne le nombre de predecesseurs)
	 */
	public int degreEntrant(int i) {
		//PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::degreEntrant("+i+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			
		int nb = 0;
		for (int j=0; j<NMAX; j++) {
			if (existeArc(j,i))
				nb++;
		}		
		return nb;
	}
	
	
	/**
	 * @param i num�ro du sommet dont on cherche le degr� positif
	 * @return retourne le nombre d'arcs dont i est l'origine (cad retourne le nombre de successeurs)
	 */
	public int degreSortant(int i) {
		//PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::degreSortant("+i+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}					
		int nb = 0;
		for (int j=0; j<NMAX; j++) {
			if (existeArc(i,j))
				nb++;
		}		
		return nb;
	}
	
	/**
	 * @param i sommet dont on cherche le degr�
	 * @return le degr� du sommet i
	 */
	public int degre(int i) {
		return degreEntrant(i) + degreSortant(i);
	}
	
//	public Vector lst_succ(int i) {
//		//PRECONDITION ... DEBUGGAGE*/
//		if (i < 0 || i >= NMAX) {
//			System.out.println("Graphe::lst_succ("+i+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
//			System.exit(-1);				
//		}			
//
//		Vector lst = new Vector(); //La liste de successeur
//		
//		if (!existeSommet(i)) {
//			return lst;
//		}
//		else {
//			//DETERMINATION DES SOMMETS SUCCESSEURS
//			for (int j=0; j<NMAX; j++) {
//				if (existeArc(i,j))
//					lst.add(new Integer(j)); //Ajout du sommet j
//			}
//		}	
//	}
	
	/**
	 * @param i le sommet dont on cherche les successeurs
	 * @return un tableau (bien dimensionn�) contenant les successeurs (num�ro de sommet) du sommet i
	 */
	public int [] lst_succ(int i) {
		//PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::lst_succ("+i+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			

		int [] lst;
		int nb = 0;
		
		if (!existeSommet(i)) {
			lst = new int[0];
			return lst;
		}
		else {
			//DETERMINATION DU NOMBRE DE SOMMETS SUCCESSEURS
			//for (int j=0; j<NMAX; j++) {
			//	if (existeArc(i,j))
			//		nb++;
			//}
			nb = degreSortant(i);
			//ALLOCATION DU TABLEAU
			lst = new int[nb]; 
			
			//REMPLISSAGE DU TABLEAU DE SOMMETS SUCCESSEURS
			int l = 0;
			for (int j=0; j<NMAX; j++) {
				if (existeArc(i,j)) {
					lst[l] = j;
					l++;
				}
			}
			return lst;
		}	
	}

	/**
	 * @param i le sommet dont on cherche les pr�d�cesseurs
	 * @return un tableau (bien dimensionn�) contenant les pr�d�cesseurs (num�ro de sommet) du sommet i
	 */
	public int [] lst_pred(int i) {
		//PRECONDITION ... DEBUGGAGE*/
		if (i < 0 || i >= NMAX) {
			System.out.println("Graphe::lst_succ("+i+"): Erreur : le sommet "+i+" est hors de l'intervalle de d�finition : [0, "+NMAX+"]");
			System.exit(-1);				
		}			

		int [] lst;
		int nb = 0;
		
		if (!existeSommet(i)) {
			lst = new int[0];
			return lst;
		}
		else {
			//DETERMINATION DU NOMBRE DE SOMMETS PREDECESSEUR
			//for (int j=0; j<NMAX; j++) {
			//	if (existeArc(j,i))
			//		nb++;
			//}
			nb = degreEntrant(i);
			//ALLOCATION DU TABLEAU
			lst = new int[nb]; 
			
			//REMPLISSAGE DU TABLEAU DE SOMMETS PREDECESSEUR
			int l = 0;
			for (int j=0; j<NMAX; j++) {
				if (existeArc(j,i)) {
					lst[l] = j;
					l++;
				}
			}
			return lst;
		}	
	}


    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString() {
    	String result="";
    	for(int i=0; i<NMAX; i++) {
    		if (existeSommet(i)) {
    			result += "("+i+"):[";
    			int [] succ = lst_succ(i);
    			if (succ.length > 0) {
    				for(int j=0; j<succ.length-1; j++) 
    					result +=  succ[j]
    						       + "<" 
    						       + getValArc(i,succ[j])
    						       +">,";
    				result +=  succ[succ.length-1]
							   + "<" 
	    					   + getValArc(i,succ[succ.length-1])
	    					   +">";
    			}
    			result += "]\n";
    		}
    	}
    	return result;
    }
	
    /**
     * @return vrai si le graphe est r�flexif (tous les sommets ont une boucle)
     */
    public boolean estReflexif() {
    	
    	boolean reflexif = true;
    	
    	for (int i=0; (i<NMAX) && reflexif; i++) {
    		if(existeSommet(i))
    			reflexif = reflexif && existeArc(i,i);    		
    	}
    	return reflexif;
    }
    
    /**
     * @return vrai si le graphe est anti-r�flexif (aucun sommet n'a de boucle)
     */
    public boolean estAntiReflexif() {
    	
    	boolean antireflexif = true;
    	
    	for (int i=0; (i<NMAX) && antireflexif; i++) {
    		if(existeSommet(i))
    			antireflexif = antireflexif && (!existeArc(i,i));    		
    	}
    	return antireflexif;
    }    
    
    /**
     * @return vrai si le graphe est sym�trique (un arc (x,y) implique l'existance de l'arc (y,x))
     * Attention, il n'y a pas de notion de valeur d'arc dans la d�finition de la sym�trie
     */
    public boolean estSymetrique() {
    	
    	boolean symetrique = true;

    	for (int i=0; (i<NMAX) && symetrique; i++) {
       		for (int j=0; j<i; j++) { //Parcour de la matrice U inf�rieure (evite de faire 2 fois le m�me test)
        		if(existeSommet(i) && existeSommet(j)) 
        			if (existeArc(i,j))
        				symetrique = symetrique && existeArc(j,i);      			
       		}
       	}
    	
    	return symetrique;
    }
    
    /**
     * @return vrai si le graphe est anti-sym�trique (un arc (x,y) interdit l'existance de l'arc (y,x) sauf si x=y)
     */
    public boolean estAntiSymetrique() {
    	
    	boolean antisymetrique = true;

    	for (int i=0; (i<NMAX) && antisymetrique; i++) {
    		//Parcour de la matrice U inf�rieur sans la diagonale ...
       		for (int j=0; j<i; j++) { //Parcour de la matrice U inf�rieure (evite de faire 2 fois le m�me test)
        		if(existeSommet(i) && existeSommet(j)) 
        			if (existeArc(i,j))
        				antisymetrique = antisymetrique && (!existeArc(j,i));      			
       		}
       	}
    	
    	return antisymetrique;
    }
    
    /**
     * @return vrai si le graphe est transitif : tout chemin de longueur deux est sous-tendu par un arc.
     */
    public boolean estTransitif() {
    	
    	boolean transitif = true;
    	
    	for (int x=0; (x<NMAX) && transitif; x++) {
        	for (int y=0; (y<NMAX) && transitif; y++) {
        		for(int z=0; (z<NMAX) && transitif; z++) {
        			if (existeArc(x,y) && existeArc(y,z))
        				transitif = transitif && existeArc(x,z);
        		}
        	}
    	}
    	
    	return transitif;
    }
 
    /**
     * @return vrai si le graphe est anti-transitif : aucun chemin de longueur deux n'est sous-tendu par un arc.
     */
    public boolean estAntiTransitif() {
    	
    	boolean transitif = true;
    	
    	for (int x=0; (x<NMAX) && transitif; x++) {
        	for (int y=0; (y<NMAX) && transitif; y++) {
        		for(int z=0; (z<NMAX) && transitif; z++) {
        			if (existeArc(x,y) && existeArc(y,z))
        				transitif = transitif && (!existeArc(x,z));
        		}
        	}
    	}
    	
    	return transitif;
    }    
    
//    public void fermetureR�flexive() {
//    }  
//    public void fermetureSymetrique() {
//    }  
//    public void fermetureAntiReflexive() {
//    }
    
    /**
     * transposition (inversion des arcs) : on transpose la matrice U ...
     */
    public void transposition() {

    	int [][] copieU = new int[NMAX][NMAX];
    	
    	//COPIE DE U
		for (int i=0; i < NMAX; i++) {				
			for (int j=0; j < NMAX; j++) {
				copieU[i][j] = U[i][j];
			}
		}
		
		//TRANSPOSITION DE LA MATRICE U
		for (int i=0; i < NMAX; i++) {				
			for (int j=0; j < NMAX; j++) {
				U[j][i] = copieU[i][j];
			}
		}
    }
    
    /**
     * @param g permet de faire l'union de 2 graphes (union ensembliste des arcs).
     * Le nombre de sommets ainsi que les num�ros de sommets doivent �tre identiques pour les deux graphes
     * La repr�sentation interne (par matrice d'adjacence) ne permet pas d'avoir plusieurs arcs entre deux 
     * m�mes sommets orient�s de la m�me facon. Dans le cas o� l'union implique deux arcs orient�s identiquement
     * entre deux m�mes sommets et ayant des valeurs diff�rentes, il faut lever une erreur (sortie de programme).
     */
    public void union(Graphe g) {
    	
		//PRECONDITION ... DEBUGGAGE*/
    	if (nbSommet() != g.nbSommet()) {
			System.out.println("Graphe::union(): Erreur : le nombre de sommet des deux graphes est diff�rent");
			System.exit(-1);
    	}
    	
		//PRECONDITION ... DEBUGGAGE*/
    	for (int i=0; i<NMAX; i++) {
    		if (existeSommet(i)!= g.existeSommet(i)) {
    			System.out.println("Graphe::union(): Erreur : Le sommet "+i+" n'est pas d�fini pour les deux graphes");
    			System.exit(-1);   			
    		}
    	}
    	

    	int [] tab_succ;
    	int j, val;
      	for (int i=0; i<NMAX; i++) {
      		if (existeSommet(i)) {
      			//EXTRACTION DES SUCCESSEURS DE i POUR LE GRAPHE g
      			tab_succ = g.lst_succ(i);
      			//PARCOUR DES SUCESSEURS ET AJOUT DES ARCS S'IL NE SONT PAS DEJA PRESENTS
      			for (int l=0; l<tab_succ.length; l++) {

      				j   = tab_succ[l];      //Le l-�me sommet successeur de i
      				val = g.getValArc(i,j); //Valeur de l'arc pour le graphe g
			
      				//DEBUGGAGE	
      				if (existeArc(i,j)) {
      					if (getValArc(i,j) != val) {
      						System.out.println("Graphe::union(): Erreur : La repr�sentation interne actuel ne permet pas d'avoir deux arcs entre deux m�me sommets");
      						System.exit(-1);   			
      					}
      				}
      				else {
      					ajoutArc(i,j, val); //Ajout de l'arc dans le graphe courant
      				}
      	  		        	  		  
      			} //Fin du for (int l ...
      		} //Fin du if
      	} //Fin du for
    }
    
    /**
     * @param g graphe avec lequel ont fait la composition
     * @return le r�sultat de la composition entre le graphe courant et le graphe g
     * la composition entre G1 et G2 donne un graphe G3 dont l'ensemble des arcs est : 
     *  { (x,y) : (x,z) est un arc de G1 et (z,y) est un arc de G2} 
     */
    public Graphe composition(Graphe g) {
    	    	
		//PRECONDITION ... DEBUGGAGE*/
    	if (nbSommet() != g.nbSommet()) {
			System.out.println("Graphe::composition(): Erreur : le nombre de sommet des deux graphes est diff�rent");
			System.exit(-1);
    	}
    	
    	Graphe compo = new Graphe(nbSommet()); //CREATION DU GRAPHE RESULTAT DE LA COMPOSITION   	
    	
    	for (int x=0; x<NMAX; x++) {
    		for (int y=0; y<NMAX; y++) {
    			for (int z=0; z<NMAX; z++) {
    				if (existeArc(x,z) && g.existeArc(z,y)) {
    					
    					//COMPOSITION A PROPREMENT PARLER
    					compo.ajoutSommet(x);
    					compo.ajoutSommet(y);
    					compo.ajoutArc(x,y, 1); //Le graphe n'est pas senss� �tre valu� ... la valeur de l'arc est donc quelconque
    				}    					
    			}
    		}
    	}
    	
    	return compo;
    }
    
    /**
     * Modifie le graphe courant en supprimant les sommets pass�s en param�tre 
     * 
     * @param lst_sommet liste des sommets � supprimer (on supprime �galement les arcs ... associ�s � ces sommets)
     * 
     */
    public void sousgraphe(int[] lst_sommet) {
    	
    	//PARCOUR DES SOMMETS A SUPPRIMER
    	for (int k=0; k<lst_sommet.length; k++) {
    		int x = lst_sommet[k]; //x est le k-�me sommet � supprimer
    		
			if (existeSommet(x)) {
				//SUPPRESSION DE TOUS LES ARCS (PARCOUR DE LA LIGNE DE NUMERO x ET DE LA COLONNE DE NUMERO x) 
				for (int y=0; y<NMAX; y++) {
					if (existeSommet(y)) {
						supprimeArc(x,y);
						supprimeArc(y,x);
					}
				}
				supprimeSommet(x); //Suppression du sommet x
			}
    	}
    }
    
	public static void main(String[] args) {
		int N = Graphe.ALPHA_NOTDEF;
		int [][] matg = { /*         0   1   2   3 */
                          /* 0 */ {  N, 11, 22, 33},
						  /* 1 */ { 44,  N,  N,  N},
						  /* 2 */ { 55,  N,  N,  N},
						  /* 3 */ { 66,  N,  N, 77} };
		Graphe g = new Graphe (matg);
		System.out.println("g.ajoutArc(1,2,3) = "+g.ajoutArc(1,2,3));
		System.out.println("g.getValArc(1,2)  = "+g.getValArc(1,2));
		//System.out.println("g.ajoutSommet(6)  = "+g.ajoutSommet(6));
		System.out.println("g.existeSommet(6) = "+g.existeSommet(6));		
		//System.out.println("g.getValArc(1,3)  = "+g.getValArc(1,3));
		//System.out.println("g.ajoutArc(1,6,100) = "+g.ajoutArc(1,6,100));
		int [] succ1 = g.lst_succ(1);
		System.out.println("Affichage des successeurs du sommet 1 :");
		for (int i=0; i<succ1.length; i++) {
			System.out.print(succ1[i]+" ");
		}
		System.out.println();
		//System.out.println("g.supprimeArc(1,6)  = "+g.supprimeArc(1,6));
		//System.out.println("g.supprimeSommet(6) = "+g.supprimeSommet(6));
		int [] succ1B = g.lst_succ(1);
		System.out.println("Affichage des successeurs du sommet 1 :");
		for (int i=0; i<succ1B.length; i++) {
			System.out.print(succ1B[i]+" ");
		}
		System.out.println();
		int [] pred1 = g.lst_pred(1);
		System.out.println("Affichage des pr�decesseur du sommet 1 :");
		for (int i=0; i<pred1.length; i++) {
			System.out.print(pred1[i]+" ");
		}		
		System.out.println();
		System.out.println("Affichage du graphe sous forme : ''(sommet) : [liste des successeur]''");
		System.out.println(g);
		
		int [][] matg2 = { /*         0   1   2   3 */
                		   /* 0 */ {  N, 11,  N, N},
						   /* 1 */ { 44,  N,  N,  N},
						   /* 2 */ { 55,  N,  3,  N},
						   /* 3 */ { 66,  N,  N, 77} };
		Graphe g2 = new Graphe(matg2); 
		g.union(g2);
		System.out.println("g = g union g2 : ");
		System.out.println(g);
		
		System.out.println("Composition de g avec g : g3 = g 'rond' g");
		Graphe g3 = g.composition(g);
		System.out.println(g3);
		
		System.out.println("g4 :");
		Graphe g4 = new Graphe(matg);
		System.out.println(g4);
		System.out.println("Transposition de g4 :");
		g4.transposition();
		System.out.println(g4);
				
		System.out.println("g4.estReflexif()      : "+ g4.estReflexif());
		System.out.println("g4.estAntiReflexif()  : "+ g4.estAntiReflexif());
		System.out.println("g4.estSymetrique()    : "+ g4.estSymetrique());
		System.out.println("g4.estAntiSymetrique(): "+ g4.estAntiSymetrique());
		System.out.println("g4.estTransitif()     : "+ g4.estTransitif());
		System.out.println("g4.estAntiTransitif() : "+ g4.estAntiTransitif());
		
		int[] lst_SommetASupprimer ={1,3}; 
		g4.sousgraphe(lst_SommetASupprimer);
		System.out.println("Sous graphe de g4 :");
		System.out.println(g4);		
		
	}
}
